class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int ret = nums[0];

        // f[i]表示以i位置为结尾的乘积最大子数组
        // g[i]表示以i位置为结尾的乘积最小子数组
        vector<__int128_t> f(n), g(n);

        // f[i]
        // 长度为1: nums[i]
        // 长度大于1且nums[i] > 0: f[i - 1] * nums[i]
        // 长度大于1且nums[i] < 0: g[i - 1] * nums[i]

        // g[i]
        // 长度为1: nums[i]
        // 长度大于1且nums[i] > 0: g[i - 1] * nums[i]
        // 长度大于1且nums[i] < 0: f[i - 1] * nums[i]

        f[0] = g[0] = nums[0];
        for(int i = 1; i < n; i++)
        {
            __int128_t x = nums[i], a = (__int128_t)g[i - 1] * nums[i], b = (__int128_t)f[i - 1] * nums[i];
            f[i] = max(x, max(a, b));
            g[i] = min(x, min(a, b));

            ret = max((int)f[i], ret);
        }
        return ret;
    }
};